import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=216 lang=java
 *
 * [216] 组合总和 III
 */

// @lc code=start
class Solution {
    LinkedList<Integer> path;
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum3(int k, int n) {
        path=new LinkedList<>();
        res=new ArrayList<>();
        dfs(k, n, 0, 1);
        return res;
    }

    public void dfs(int k,int target,int sum,int startIndex){
        //剪枝
        if(sum>target) return;
        if(path.size()==k){
            if(sum==target) res.add(new LinkedList<>(path));
            return;
        }
        for(int i=startIndex;i<=9-(k-path.size())+1;i++){
            path.add(i);
            sum+=i;
            dfs(k, target, sum, i+1);
            sum-=i;
            path.removeLast();
        }
    }
}
// @lc code=end

